#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define maxsize 100

typedef struct {
    int col[maxsize];
    int top;
} stacktype;

void display(stacktype st) {
    static int count = 0;
    printf("第%d个解", ++count);
    for (int i = 1; i <= st.top; i++)
        printf("(%d,%d)", i, st.col[i]);
    printf("\n");
}

bool place(stacktype st, int k, int j) {
    int i = 1;
    if (k == 1) return true;
    while (i <= k - 1) {
        if ((st.col[i] == j) || (abs(j - st.col[i]) == abs(i - k)))
            return false;
        i++;
    }
    return true;
}

void queen(int n) {
    int k;
    bool find;
    stacktype st;
    st.top = 0;
    st.top++;
    st.col[st.top] = 0;
    while (st.top != 0) {
        k = st.top;
        find = false;
        for (int j = st.col[k] + 1; j <= n; j++) {
            if (place(st, k, j)) {
                st.col[st.top] = j;
                find = true;
                break;
            }
            if (find) {
                if (k == n)
                    display(st);
                else {
                    st.top++;
                    st.col[st.top] = 0;
                }
            } else
                st.top--;
        }
    }
}

int main() {
    int n;
    printf("皇后问题(n<20)n=");
    scanf("%d", &n);
    if (n > 20)
        printf("n值太大\n");
    else {
        printf("%d皇后问题求解如下\n", n);
        queen(n);
    }
    return 1;
}
